#define _CRT_SECURE_NO_WARNINGS 1

#include <iostream>
#include <vector>
#include <climits>

using namespace std;

const int INF = INT_MAX;

void prim(int startVertex,int numVertices,vector<vector<int>>& adjacencyMatrix)
{
	vector<bool> visited(numVertices, false); 
	visited[startVertex] = true;

	int totalWeight = 0; 

	for (int count = 1; count < numVertices; ++count)
	{
		int minWeight = INT_MAX;
		int minVertex;

		for (int v = 0; v < numVertices; ++v)
		{
			if (visited[v])
			{
				for (int u = 0; u < numVertices; ++u)
				{
					if (!visited[u] && v!=u && adjacencyMatrix[v][u] < minWeight)
					{
						startVertex = v;
						minWeight = adjacencyMatrix[v][u];
						minVertex = u;
					}
				}
			}
		}
		totalWeight += minWeight;
		visited[minVertex] = true;
		startVertex = minVertex;
	}
	cout << totalWeight << endl;
}

void test6(int n)
{
	//int n;
	//cin >> n;
	vector<vector<int>> distances(n, vector<int>(n));
	for (int i = 0; i < n; ++i)
	{
		for (int j = 0; j < n; ++j)
		{
			cin >> distances[i][j];
		}
	}
	int q;
	cin >> q;
	vector<vector<bool>> connected(n, vector<bool>(n, false));
	for (int i = 0; i < q; i++)
	{
		int a, b;
		cin >> a >> b;
		connected[a - 1][b - 1] = true;
		connected[b - 1][a - 1] = true;
		distances[a - 1][b - 1] = 0;
		distances[b - 1][a - 1] = 0;
	}

	prim(0, n, distances);

	//for (int k = 0; k < n; k++)
	//{
	//	for (int i = 0; i < n; i++)
	//	{
	//		for (int j = 0; j < n; j++)
	//		{
	//			distances[i][j] = min(distances[i][j], distances[i][k] + distances[k][j]);
	//		}
	//	}
	//}
	//int totaldis = 0;
	//for (int i = 0; i < n; ++i)
	//{
	//	for (int j = i + 1; j < n; ++j)
	//	{
	//		if (!connected[i][j])
	//		{
	//			totaldis += distances[i][j];
	//		}
	//	}
	//}
	//cout << totaldis << endl;
}

int main()
{
	int n;
	//int t;
	//cin >> t;
	while (scanf("%d", &n) != EOF)
	{
		test6(n);
	}

	return 0;
}